class Solution(object):
    def maximumMinimumPath(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        m = len(grid)
        n = len(grid[0])
        path_grid = [[-1 for _ in range(n)] for _ in range(m)]
        path_grid[0][0] = grid[0][0]
        now_set = {(0, 0)}

        def search(x, y):
            for ux, uy in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:
                if 0 <= ux < m and 0 <= uy < n:
                    min_value = min(grid[ux][uy], path_grid[x][y])
                    if min_value > path_grid[ux][uy]:
                        path_grid[ux][uy] = min_value
                        next_set.add((ux, uy))

        while now_set:
            next_set = set()
            for point in now_set:
                search(point[0], point[1])
            now_set = next_set

        return path_grid[-1][-1]


data = Solution()
grid = [[5, 4, 5], [1, 2, 6], [7, 4, 6]]
print(data.maximumMinimumPath(grid))
grid = [[2, 2, 1, 2, 2, 2], [1, 2, 2, 2, 1, 2]]
print(data.maximumMinimumPath(grid))
grid = [[3, 4, 6, 3, 4], [0, 2, 1, 1, 7], [8, 8, 3, 2, 7], [3, 2, 4, 9, 8], [4, 1, 2, 0, 0], [4, 6, 5, 4, 3]]
print(data.maximumMinimumPath(grid))
